//
//  ClockwiseTraveler.m
//  Henry
//
//  Created by Ron Olson on 3/12/10.
//  Copyright 2010 Keep Bertha Surfin. All rights reserved.
//

#import "ClockwiseTraveler.h"
#import "NearestNeighbor.h"

@implementation ClockwiseTraveler

-(id)initWithWaypoints:(NSArray*)waypointList startingAt:(Waypoint*)firstWaypoint
{
	if (![super init])
		return nil;
	
	waypoints = waypointList;
	originPoint = firstWaypoint;
	
	optimizedList = [[NSMutableArray alloc] init];
	
	/* And add our origin point as the start of the list of optimized points */
	[optimizedList addObject:originPoint];
	
	/* And allocate the work lists */
	nwList = [[NSMutableArray alloc] init];
	neList = [[NSMutableArray alloc] init];
	seList = [[NSMutableArray alloc] init];
	swList = [[NSMutableArray alloc] init];
	
	return self;	
}

-(NSArray*)getSortedWaypoints
{
	[self createTour];
	
	return optimizedList;
}

-(void)createTour
{
	[self fillCompassLists];
	
	/*
	 * Now run nearest-neighbor on each of the lists, where we use our
	 * starting point (this.startingPoint) as the starting point for the NW
	 * list, then we use the last item of each of the previous lists to
	 * chain them together. If a list doesn't have any elements, we revert
	 * to our original starting point.
	 */
	NearestNeighbor *nwNN = [[NearestNeighbor alloc] initWithWaypoints:nwList startingAt:originPoint];
	NearestNeighbor *neNN = [[NearestNeighbor alloc] initWithWaypoints:neList startingAt:[nwList count] == 0 ? originPoint : [nwList lastObject]];
	NearestNeighbor *seNN = [[NearestNeighbor alloc] initWithWaypoints:seList startingAt:[neList count] == 0 ? originPoint : [neList lastObject]];
	NearestNeighbor *swNN = [[NearestNeighbor alloc] initWithWaypoints:swList startingAt:[seList count] == 0 ? originPoint : [seList lastObject]];
	
	[optimizedList addObjectsFromArray:[nwNN getSortedWaypoints]];
	[optimizedList addObjectsFromArray:[neNN getSortedWaypoints]];
	[optimizedList addObjectsFromArray:[seNN getSortedWaypoints]];
	[optimizedList addObjectsFromArray:[swNN getSortedWaypoints]];
}

/*
 * The starting point is in the center of four squares, labeled NW, NE, SW,
 * SE. All the waypoints must fall into one of those squares, based on where
 * each point is from the center, starting point (this.startingPoint).
 * 
 * Note: This assumes you're not standing on the equator or at the prime
 * meridian
 */
-(void)fillCompassLists
{
	for(Waypoint *wp in waypoints)
	{
		/*
		 * If this latitude is less than the starting point (higher) and the
		 * longitude is greater than the starting point (to the left), put
		 * it in the NW list.
		 */
		if ([wp latitude] > [originPoint latitude] && [wp longitude] < [originPoint longitude])
		{
			[nwList addObject:wp];
		}
		/*
		 * If this latitude is less than the starting point (higher) and the
		 * longitude is less than the starting point (to the right), put it
		 * in the NE list.
		 */
		else if ([wp latitude] > [originPoint latitude] && [wp longitude] > [originPoint longitude])
		{
			[neList addObject:wp];
		}
		/*
		 * If this latitude is greater than the starting point (lower) and
		 * the longitude is greater than the starting point (to the left),
		 * put it in the SW list.
		 * 
		 * Note, we compare wp as greater than to the starting point,
		 * because the number is greater than another if it's closer to
		 * zero.
		 */
		else if ([wp latitude] < [originPoint latitude] && [wp longitude] < [originPoint longitude])
		{
			[swList addObject:wp];
		}
		/*
		 * If this latitude is greater than the starting point (lower) and
		 * the longitude is less than the starting point (to the right), put
		 * it in the SE list. Note, we compare wp as greater than to the
		 * starting point, because the number is greater than another if
		 * it's closer to zero.
		 */
		else if ([wp latitude] < [originPoint latitude] && [wp longitude] > [originPoint longitude])
		{
			[seList addObject:wp];
		}
	}
}

@end
